package lc_337_打家劫舍_III;

public class Solution {

	/**
	 * Definition for a binary tree node.
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	private int[] f(TreeNode root) {
		if (root == null) {
			return new int[] { 0, 0 };
		}
		int[] l = f(root.left), r = f(root.right);
		int a = root.val + l[0] + r[0], b = l[1] + r[1];
		return new int[] { b, Math.max(a, b) };
	}

	public int rob(TreeNode root) {
		return f(root)[1];
	}

}